package cn.icybear.orzjisp.bytefile;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.Arrays;

public class LineNumberTable implements Section, OrzConstants {

	// public LinkedList<LineNumberPair> linePairs = new
	// LinkedList<LineNumberPair>();

	protected int[] offsets;
	protected int[] lineNums;

	protected int count;

	public LineNumberTable() {
		offsets = new int[32];
		lineNums = new int[32];
	}

	public LineNumberTable(DataInputStream is) throws IOException {
		if (TAG_LINE_NUMBER_TABLE != is.readUnsignedByte())
			throw new IOException("unexcepted tag");
		@SuppressWarnings("unused")
		int len = is.readInt();
		count = is.readUnsignedShort();
		lineNums = new int[count];
		offsets = new int[count];

		for (int i = 0; i < count; i++) {
			offsets[i] = is.readUnsignedShort();
			lineNums[i] = is.readUnsignedShort();
		}
	}

	public void addLine(int offset, int line) {
		count++;
		if (count > lineNums.length) {
			lineNums = Arrays.copyOf(lineNums, lineNums.length << 1);
			offsets = Arrays.copyOf(offsets, offsets.length << 1);
		}
		lineNums[count] = line;
		offsets[count] = offset;
	}

	public int findLine(int offset) {
		int x = Arrays.binarySearch(offsets, offset);
		x = x >= 0 ? x : -(x + 1) - 1;
		if (x >= count || x < 0)
			return -1;
		else
			return lineNums[x];
	}

	@Override
	public void writeTo(OutputStream out) throws IOException {
		DataOutputStream writer = (out instanceof DataOutputStream) ? (DataOutputStream) out
				: new DataOutputStream(out);
		writer.writeByte(TAG_LINE_NUMBER_TABLE);
		writer.writeInt(size());
		writer.writeShort(count);
		sort1(offsets, lineNums, 0, count);
		for (int i = 0; i < count; i++) {
			writer.writeShort(offsets[i]);
			writer.writeShort(lineNums[i]);
		}
	}

	@Override
	public int size() {
		return count * 4 + 2;
	}

	@Override
	public int getLength() {
		return size() + 5;
	}

	@Override
	public int getTag() {
		return TAG_LINE_NUMBER_TABLE;
	}

	@Override
	public boolean isReadonly() {
		return false;
	}

	@Override
	public void setTag(int tag) {
		throw new UnsupportedOperationException();
	}

	/**
	 * From Sun JDK 1.6 Source.
	 * Sorts the specified sub-array of integers into ascending order.
	 */
	private static void sort1(int x[], int y[], int off, int len) {
		// Insertion sort on smallest arrays
		if (len < 7) {
			for (int i = off; i < len + off; i++)
				for (int j = i; j > off && x[j - 1] > x[j]; j--) {
					swap(x, j, j - 1);
					swap(y, j, j - 1);
				}
			return;
		}

		// Choose a partition element, v
		int m = off + (len >> 1); // Small arrays, middle element
		if (len > 7) {
			int l = off;
			int n = off + len - 1;
			if (len > 40) { // Big arrays, pseudomedian of 9
				int s = len / 8;
				l = med3(x, l, l + s, l + 2 * s);
				m = med3(x, m - s, m, m + s);
				n = med3(x, n - 2 * s, n - s, n);
			}
			m = med3(x, l, m, n); // Mid-size, med of 3
		}
		int v = x[m];

		// Establish Invariant: v* (<v)* (>v)* v*
		int a = off, b = a, c = off + len - 1, d = c;
		while (true) {
			while (b <= c && x[b] <= v) {
				if (x[b] == v) {
					swap(x, a, b);
					swap(y, a++, b);
				}
				b++;
			}
			while (c >= b && x[c] >= v) {
				if (x[c] == v) {
					swap(x, c, d);
					swap(y, c, d--);
				}
				c--;
			}
			if (b > c)
				break;
			swap(x, b, c);
			swap(y, b++, c--);
		}

		// Swap partition elements back to middle
		int s, n = off + len;
		s = Math.min(a - off, b - a);
		vecswap(x, off, b - s, s);
		vecswap(y, b, n - s, s);
		s = Math.min(d - c, n - d - 1);
		vecswap(x, b, n - s, s);
		vecswap(y, b, n - s, s);
		// Recursively sort non-partition-elements
		if ((s = b - a) > 1)
			sort1(x, y, off, s);
		if ((s = d - c) > 1)
			sort1(x, y, n - s, s);
	}

	private static void swap(int x[], int a, int b) {
		int t = x[a];
		x[a] = x[b];
		x[b] = t;
	}

	private static void vecswap(int x[], int a, int b, int n) {
		for (int i = 0; i < n; i++, a++, b++)
			swap(x, a, b);
	}

	private static int med3(int x[], int a, int b, int c) {
		return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
				: (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
	}

}
